//给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。 
//
// 已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。 
//
// 每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎
//，则可以在之后的操作中 重复使用 这枚鸡蛋。 
//
// 请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？ 
// 
//
// 示例 1： 
//
// 
//输入：k = 1, n = 2
//输出：2
//解释：
//鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。 
//否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。 
//如果它没碎，那么肯定能得出 f = 2 。 
//因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。 
// 
//
// 示例 2： 
//
// 
//输入：k = 2, n = 6
//输出：3
// 
//
// 示例 3： 
//
// 
//输入：k = 3, n = 14
//输出：4
// 
//
// 
//
// 提示： 
//
// 
// 1 <= k <= 100 
// 1 <= n <= 10⁴ 
// 
// Related Topics数学 | 二分查找 | 动态规划 
//
// 👍 852, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.Arrays;

class SuperEggDrop {
    public static void main(String[] args) {
        Solution solution = new SuperEggDrop().new Solution();
        solution.superEggDrop(1, 2);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // 超时：
    /*class Solution {
        int[][] memo;   // 备忘录

        public int superEggDrop(int k, int n) {
            memo = new int[k + 1][n + 1];
            for (int[] ints : memo) {
                Arrays.fill(ints, -999);
            }

            return dp(k, n);
        }

        // 表示从该楼层抛k个鸡蛋的最小操作数
        private int dp(int k, int n) {
            if (k == 1) return n; // 鸡蛋数未1，只能线性遍历
            if (n == 0) return 0; // 0层就不需要抛

            if (memo[k][n] != -999) {
                return memo[k][n];
            }


            int res = Integer.MAX_VALUE;
            for (int i = 1; i <= n; i++) {
                // 最坏情况下扔鸡蛋的最小次数
                res = Math.min(res,
                        // 鸡蛋碎了：搜下下边
                        // 鸡蛋没碎：搜索上边
                        Math.max(
                                dp(k, n - i),
                                dp(k - 1, i - 1)
                        ) + 1
                );
            }

            memo[k][n] = res;
            return res;
        }
    }*/

    class Solution {
        int[][] memo;   // 备忘录

        public int superEggDrop(int k, int n) {
            memo = new int[k + 1][n + 1];
            for (int[] ints : memo) {
                Arrays.fill(ints, -999);
            }

            return dp(k, n);
        }

        // 二分搜索替换
        // 表示从该楼层抛k个鸡蛋的最小操作数
        private int dp(int k, int n) {
            if (k == 1) return n; // 鸡蛋数未1，只能线性遍历
            if (n == 0) return 0; // 0层就不需要抛

            if (memo[k][n] != -999) {
                return memo[k][n];
            }


            int res = Integer.MAX_VALUE;
            int l = 1, r = n;
            while (l <= r) {
                int m = l + (r - l) / 2;
                int broken = dp(k - 1, m - 1);
                int no_broken = dp(k, n - m);
                if (broken > no_broken) {
                    r = m - 1;
                    res = Math.min(res, broken + 1);
                } else {
                    l = m + 1;
                    res = Math.min(res, no_broken + 1);
                }
            }

            memo[k][n] = res;
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
